package com.csci;

import java.util.LinkedList;

public class BackTrackAlgorithm {

	public static int backTrackCounter = 0;
	boolean[] isFound = new boolean[9];
	
	public BackTrackAlgorithm() {
		resetIsFound();
	}

	public void resetIsFound() {
		for (int value = 0; value < 9; value++) {
			isFound[value] = false;
		}
	}

	public Sudoku backtrack(Sudoku s) {
		if (reject(s)) {
			return null;
		} else if (accept(s)) {
			return s;
		}
		return null;
	}

	public Sudoku backTrack(Sudoku s){
		backTrackCounter++;
		Sudoku solution = null;
		
		//If the Sudoku puzzle is wrong, return null
		if(reject(s)){
			return null;
		}
		
		//If the Sudoku state is correct, then we are done.
		else if( accept(s)){
			return s;
		}
		
		// Since we haven't a solution, get all tile possible solutions for this Sudoku puzzle
		LinkedList<CellSet> minList = getChildQueue(s);
		
		//Try a new possibility for the first unsolved tile, it will return null if we have ran out of possiblities for the tile
		Sudoku sudokuPrime = Sudoku.newInstance(updateSudoku(s, minList));
		
		while(sudokuPrime != null && solution == null){
			solution = Sudoku.newInstance(backTrack(sudokuPrime));
			
			//if solution is null, then the current possiblity doesn't work and remove it. PRUNING HERE!
			minList.get(0).set.pop(); 
			sudokuPrime = Sudoku.newInstance(updateSudoku(s, minList));
		}
		return solution;
	}
	
	public boolean reject(Sudoku s) {

		if (!checkBoxes(s)) {
			return true;
		}
		if (!checkRows(s)) {
			return true;
		}

		if (!checkCols(s)) {
			return true;
		}
		return false;
	}

	public boolean checkBox(Sudoku s, int rowStart, int rowStop, int colStart, int colStop) {
		resetIsFound();
		for (int row = rowStart; row < rowStop; row++) {
			for (int col = colStart; col< colStop; col++) {
				if (s.puzzleGrid[row][col] == -1) {
					continue;
				} else if (isFound[s.puzzleGrid[row][col] - 1] == true) {
					return false;
				} else {
					isFound[s.puzzleGrid[row][col] - 1] = true;
				}
			}
		}
		return true;
	}

	public boolean checkBoxes(Sudoku s) {
		for (int puzzleRow = 0; puzzleRow < 3; puzzleRow++) {
			for (int puzzleCol = 0; puzzleCol < 3; puzzleCol++) {
				PuzzleBox pb = convertPuzzleTileToBox(puzzleRow, puzzleCol);
				if (!checkBox(s, pb.rowStart, pb.rowStop, pb.colStart, pb.colStop)) {
					return false;
				}
			}
		}
		return true;
	}

	public static PuzzleBox convertPuzzleTileToBox(int boxRow, int boxCol){
		
		//row 0
		if(boxRow == 0 && boxCol == 0){
			return new PuzzleBox(0,3, 0, 3);
		}
		else if(boxRow == 0 && boxCol == 1){
			return new PuzzleBox(0,3, 3, 6);
		}
		else if(boxRow == 0 && boxCol == 2){
			return new PuzzleBox(0,3, 6, 9);
		}
		
		
		//row 1
		else if(boxRow == 1 && boxCol == 0){
			return new PuzzleBox(3,6, 0, 3);
		}
		else if(boxRow == 1 && boxCol == 1){
			return new PuzzleBox(3,6, 3, 6);
		}
		else if(boxRow == 1 && boxCol == 2){
			return new PuzzleBox(3,6, 6, 9);
		}
		
		//row 2
		else if(boxRow == 2 && boxCol == 0){
			return new PuzzleBox(6,9, 0, 3);
		}
		else if(boxRow == 2 && boxCol == 1){
			return new PuzzleBox(6,9, 3, 6);
		}
		else if(boxRow == 2 && boxCol == 2){
			return new PuzzleBox(6,9, 6, 9);
		}
		
		
		return null;
	}
	
	public boolean checkRows(Sudoku s) {
		for (int row = 0; row < 9; row++) {
			resetIsFound();
			for (int col = 0; col < 9; col++) {
				if (s.puzzleGrid[row][col] == -1) {
					continue;
				} else if (isFound[s.puzzleGrid[row][col] - 1] == true) {
					return false; // return false if checkingRows fails
				} else {
					isFound[s.puzzleGrid[row][col] - 1] = true;
				}
			}
		}
		return true;
	}

	public boolean checkCols(Sudoku s) {
		for (int col = 0; col < s.dimension; col++) {
			resetIsFound();
			for (int row = 0; row < s.dimension; row++) {
				if (s.puzzleGrid[row][col] == -1) {
					continue;
				} else if (isFound[s.puzzleGrid[row][col] - 1] == true) {
					return false;
				} else {
					isFound[s.puzzleGrid[row][col] - 1] = true;
				}
			}
		}
		return true;
	}

	public boolean accept(Sudoku s) {
		for (int row = 0; row < 9; row++) {
			for (int col = 0; col < 9; col++) {
				if (s.puzzleGrid[row][col] == -1) {
					return false;
				}
			}
		}
		return true;
	}

	//create a set for every possible unfilld square
	public LinkedList<CellSet> getChildQueue(Sudoku sudoku) {
		LinkedList<CellSet> minList = new LinkedList<CellSet>();
		for (int puzzleRow = 0; puzzleRow < 9; puzzleRow++) {
			for (int puzzleCol = 0; puzzleCol < 9; puzzleCol++) {
				CellSet cellSet = new CellSet(puzzleRow, puzzleCol);
				cellSet.set = Possibilities.getPossibilities(sudoku, puzzleRow, puzzleCol);//smart way, calls back track 392 time to solve a blank puzzle and 322 to solve a partially filled in solution, it took 16273 backtrack calls for 4puz.com really hard, volume 1 page 1, puzzle 1)
				//cellSet.set= Possibilities.getPossibilitiesBruteForce(sudoku, puzzleRow, puzzleCol);// takes 3196 to solve a blank puzzle, it took 146207 backtrack calls for 4puz.com puzzle.
				if (cellSet.set != null) {
					minList.addFirst(cellSet);
				}
			}
		}
		return minList;
	}
	
	public Sudoku updateSudoku(Sudoku s, LinkedList<CellSet> minList){
		if(minList.get(0).set.size() == 0){
			return null;
		}
		else{
			s.puzzleGrid[minList.get(0).row][minList.get(0).col] = minList.get(0).set.get(0);
			return s;
		}
	}
}
